COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00035 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A96.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 22, 1988}
\leftline{\sevenrm Unpublished draft}
\font\sevenit=cmti7
\scriptfont\itfam=\sevenit
\bigskip
\noindent {\bf Acceptors, Recognizers, and Classifiers}
\medskip
Let $L$ be a language (set of strings) over the alphabet $\Sigma$.
Consider programs with domain $\Sigma↑*$ where $\alpha↓{\it input} =
\delta$ and $\alpha$ for other devices is independent of
the argument, there is no output device, and the range is $\{\it True, False\}$.
Such a program is called an {\it acceptor} for $L$ if $\tau\circ\{\it True\}
= L$.

It is a {\it co-acceptor} for $L$ if $\tau\circ\{\it False\} = {\overline L}$.
That is, by changing $\omega$ in the obvious way, a co-acceptor for $L$
is an acceptor for ${\overline L}$.  A program is a {\it recognizer} for $L$
if it is deterministic, an acceptor, and a co-acceptor.  By twiddling $\omega$,
a recognizer for $L$ becomes a recognizer for ${\overline L}$.

If such a machine starts and ends with all memory devices in a standard
state (say, stacks and queues empty, counters zero), the definitions of $\alpha$
and $\omega$ for each device are:
$$\eqalign{\alpha↓{\it memory} & =  \Sigma↑* \times \{\it standard\, state\},\cr
\omega↓{\it memory} & =  \{\it standard\, state\} \times \{\it True, False\},\cr
\alpha↓{\it input} & =  \delta,\cr
\omega↓{\it input} & =  \Lambda\times\{\it True, False\},\cr
\alpha↓{\it control} & =  \Sigma↑*\times Q↓{\it start}, \hbox {where}\; 
Q↓{\it start}
\subseteq Q,\cr
\omega↓{\it control} & =  Q↓{\it accept} \times \{{\it True}\}\cup Q↓{\it reject}
\times \{{\it False}\}, 
\hbox {where}\; Q↓{\it accept} \subseteq Q, Q↓{\it reject}
\subseteq Q.\cr}$$
The notion of a recognizer can be generalized to that of a {\it classifier}, where
the range is a finite set $Y$, and $\omega↓{\it control}$ is a partial function
from $Q$ to $Y$, the program is deterministic, and its transfer function is total.

An acceptor for a language $L$ can easily be transformed into a program that
{\it generates} $L$; replace the input device with an output device, and replace
each instruction in the
acceptor program that scans input, $\langle i\rightarrow j, \hbox {scan}\, a, f
\rangle$, by $\langle i\rightarrow j, \hbox {write}\,
a, f\rangle$.  Notice that a deterministic acceptor, in general, transforms to a
nondeterministic generator.

Similarly, an acceptor for $L$ can be transformed into a transducer with 
transfer relation $\delta↓L$; add an output device, and replace each
acceptor instruction $\langle i\rightarrow j, \hbox {scan}\, a, f\rangle$ that
scans input by $\langle i\rightarrow j, \hbox {scan}\, a, f, \hbox {write}\,
 a\rangle$.
Such a transducer, which passes from input to output precisely the elements
of the language $L$, is called a {\it filter}.
\vfill\eject
\noindent{\bf Standardizing a finite machine\hfill}
\medskip
Let $P$ be a program for a {\it finite machine\/} $M$, i.e., a~machine
with devices $\langle$control, input, output$\rangle$. We transform $P$
into~$P'$ that simulates~$P$ but uses scan, eof, and noop as its only
input operations. For each state $i\in Q$, there are states~$i↓{\Lambda}$
and $i↓{\rm end}\in Q'$. Additionally, for each $a\in\Sigma$, $i↓a\in Q'$.

The simulation relation $\rho$ is a partial function
$$\eqalign{&\langle i↓{\Lambda},x,y\rangle\;\rho\;\langle i,x,y\rangle\cr
&\langle i↓a,x,y\rangle\;\rho\;\langle i,ax,y\rangle\cr
&\langle i↓e,\Lambda,y\rangle\;\rho\;\langle i,\Lambda,y\rangle\,.\cr}$$
If $Q↓{\alpha}=\{i\}$, then $Q'↓{\alpha}=\{i↓{\Lambda}\}$. For
$j\in Q↓{\omega}$, $j↓{\rm end}\in Q'↓{\omega}$.

\bigskip
$$\vcenter{\halign{\hfil$#$\hfil\qquad&\hfil$#$\hfil\qquad&$\hfil#\hfil$\cr
&\alpha&\langle i,u,\Lambda\rangle\cr
\noalign{\smallskip}
u&&\rho\cr
\noalign{\smallskip}
&\alpha'&\langle i↓{\Lambda},u,\Lambda\rangle\cr
\noalign{\bigskip\bigskip}
\langle j,\Lambda,v\rangle&\omega\cr
\noalign{\smallskip}
\rho&&v\cr
\noalign{\smallskip}
\langle j↓{\rm end},\Lambda,v\rangle&\omega'\cr}}$$

\bigskip
\noindent
The diagrams above show the beginning and end of the simulation. The other
components are these:

\bigskip
$$\vcenter{\offinterlineskip%
\halign{\hfil$#$\hfil\qquad&$\hfil#\hfil$\qquad&\hfil$#$\hfil\qquad
&$\hfil#\hfil$\qquad&\hfil$#$\hfil\cr
&&\langle i,ax,y\rangle\cr
\noalign{\medskip}
&\rho&&\rho\cr
\noalign{\medskip}
&&\langle i↓{\Lambda}→i↓a,{\rm scan}\;a,{\rm noop}\rangle\cr
\langle i↓{\Lambda},ax,y\rangle&&&&\langle i↓a,x,y\rangle\cr
\noalign{\bigskip\bigskip}
&&\langle i,\Lambda,y\rangle\cr
\noalign{\medskip}
&\rho&&\rho\cr
\noalign{\medskip}
&&\langle i↓{\Lambda}→i↓{\rm end},{\rm eof},{\rm noop}\cr
\langle i↓{\Lambda},\Lambda,y\rangle&&&&\langle i↓{\rm end},\Lambda,y\rangle\cr}}$$

\medskip
\noindent
for all $i\in Q$, $a\in\Sigma$.

\vfill\eject
Additionally, for each instruction in $P$, there is a simulating instruction
in~$P'$.

\bigskip
$$\vcenter{\offinterlineskip%
\halign{\hfil$#$\hfil\qquad&$\hfil#\hfil$\qquad&\hfil$#$\hfil\cr
&\langle i→j,{\rm next}\; a,{\rm write}\; b\rangle\cr
\langle i,ax,y\rangle&&\langle j,ax,yb\rangle\cr
\noalign{\smallskip}
\rho &&\rho\cr
\noalign{\smallskip}
&\langle i↓a→j↓a,{\rm noop},{\rm write}\; b\rangle\cr
\langle i↓a,x,y\rangle&&\langle j↓a,x,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm scan}\;a,{\rm write}\;b\rangle\cr
\langle i,ax,y\rangle&&\langle j,x,yb\rangle\cr
\noalign{\smallskip}
\rho&& \rho\cr
\noalign{\smallskip}
&\langle i↓a→j↓{\Lambda},{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓a,x,y\rangle&&\langle j↓{\Lambda},x,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm eof},{\rm write}\;b\rangle\cr
\langle i,\Lambda,y\rangle&&\langle j,\Lambda,yb\rangle\cr
\noalign{\smallskip}
 \rho&&\rho\cr
\noalign{\smallskip}
&\langle i↓{\rm end}→j↓{\rm end},{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓{\rm end},\Lambda,y\rangle&&\langle j↓{\rm end},\Lambda,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm noop},{\rm write}\;b\rangle\cr
\langle i,ax,y\rangle&&\langle j,ax,yb\rangle\cr
\noalign{\smallskip}
\rho&&\rho\cr
\noalign{\smallskip}
&\langle i↓a→j↓a,{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓a,x,y\rangle&&\langle j↓a,x,yb\rangle\cr
\noalign{\bigskip\bigskip}
&\langle i→j,{\rm noop},{\rm write}\;b\rangle\cr
\langle i,\Lambda,y\rangle&&\langle j↓a,x,yb\rangle\cr
\noalign{\smallskip}
\noalign{\bigskip}
\noalign{\smallskip}
&\langle i↓{\rm end}→j↓{\rm end},{\rm noop},{\rm write}\;b\rangle\cr
\langle i↓{\rm end},\Lambda,y\rangle&&\langle j↓{\rm end},\Lambda,yb\rangle\cr}}$$

\noindent
where $b\in\Delta↑{\ast}$, write $\Lambda$ is the same as noop. Every instruction
of~$P$ can be simulated by one or two of~$P'$.

By inspecting the instructions of $P'$, one sees:

\smallskip
\display 20pt:$\bullet$:
End states lead only to end states.

\smallskip
\display 20pt:$\bullet$:
Instructions that go from non-end states to end states are the same as those
that execute eof.

\smallskip
\display 20pt:$\bullet$:
Initial states are not end states.

\smallskip
\display 20pt:$\bullet$:
Terminal states are end states.

\smallskip
\display 20pt:$\bullet$:
End states use only noop as the input operation.

\smallskip
\display 20pt:$\bullet$:
Eof, scan, and noop are the only input operations.

\smallskip
\display 20pt:$\bullet$:
Every instruction has a noop as its input operation, its output operation,
or both.

\smallskip
We conclude that any path through $P$ contains as its non-trivial input
operations a sequence of scans followed by an eof. Therefore every path is
executable, with uniquely defined input and output strings. If each arc in the
graph of the program is given a unique label, a~regular expression may be
constructed (Kleene's theorem) for the set of executable paths. By substituting
for the labels the characters scanned or~$\Lambda$s, one gets a regular
expression for the strings accepted. Similarly, one constructs a regular
expression for the strings written by accepting computations, and for the
traces of accepting computations.

Clearly a control state may occur in an accepting computation only if it lies
on a path from an initial state to an accepting state in the control graph.
All other states can be replaced by rejecting halts. If $\phi$ is the arc
relation in the control graph, one can construct $\phi↑{\ast}$ and test,
for each control state~$i$, whether $Q↓{\alpha}\,\phi↑{\ast}\,i$ and
whether $i\,\phi↑{\ast}\,Q↓{\omega}$. Unreachable states, in fact, can be
omitted from~$Q$.

A rejecting state $i$ that is not an end state may be reached without
consuming all input. We can make it consume all input by adding
$\langle i→i,{\rm scan}\;a,{\rm noop}\rangle$ for each $a\in\Sigma$,
and $\langle i→j,{\rm eof},{\rm noop}\rangle$, where the new state~$j$
is now the rejecting state.

Noops may be eliminated one at a time. If control state~$i$ is a noop state
(i.e., there is an instruction $\langle i→j,{\rm noop},{\rm noop}\rangle$)
then any instruction that goes to~$i$ could go directly to~$j$ instead.
If $i$ is initial, let $j$ be initial instead. Then omit $i$ and the noop
instruction. (If $j$ were equal to~$i$, state~$i$ would already have been
eliminated for never reaching a terminal state.)

After elimination of the noops, every nonterminal state~$i$ has one of two forms:

\bigskip
$$\vcenter{\halign{$\hfil#\hfil$\qquad&$\hfil#\hfil$\qquad\qquad\qquad\qquad\qquad
&$\hfil#\hfil$\qquad&$\hfil#\hfil$\qquad\cr
&&&{\rm write}\;b\cr
&{\rm scan}\;a↓1&i\cr
\noalign{\bigskip}
&{\rm scan}\;a↓2\cr
i\cr
&{\rm eof}\cr}}$$

\bigskip
\bigskip
\bigskip\noindent
If the original machine was a finite acceptor (i.e., did no writing), so is
the transformed machine, and every nonterminal state has the first form.
Then eofs lead only to terminal states.

The standardized machine always halts. It can not do as many as $|Q|$
consecutive writes (why?), and on input~$u$ can not do more than
$|u|+1$ input operations. This also shows that output length is bounded
by a linear function of input length.

\vfill\eject

$$\vcenter{\halign{\hfil#\hfil\quad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\cr
&&4&&&&&scan $b$\cr
&&\phantom{4000}$+$\cr
\noalign{\bigskip}
&&&scan $a$&&&&eof\cr
$\Rightarrow$&1&&&&&2&&5\cr
&&&&&&&&\phantom{5000}$-$\cr
&&scan $b$&&scan $b$\cr
&&&&&scan $a$\cr
&scan $a$\cr
&&&3\cr
\noalign{\bigskip}
&&&\phantom{30000}eof\cr
\noalign{\bigskip}
&&&6\cr
&&&\phantom{6000}$+$\cr}}$$

\bigskip
The above program can be abbreviated, by leaving out the terminal states,
marking the nonterminal states from which eof leads to an accepting state,
and omitting the word ``scan'':

\bigskip
$$\vcenter{\halign{\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\cr
&&&&&&&&$b$\cr
\noalign{\bigskip}
&&&&$a$\cr
$\Rightarrow$&1&&&&&&2\cr
&&&$b$&&$b$\cr
&&$a$&&&&$a$\cr
\noalign{\bigskip}
&&&&3\cr}}$$

\bigskip
\noindent
This is the traditional graphic picture of a finite acceptor.

\vfill\eject
\noindent{\bf Theorem:\hfill}

Any (partial) function that can be computed on one of these machines can be
computed on all of them:

\smallskip\disleft 25pt:(1):
2 or more stacks

\smallskip\disleft 25pt:(2):
1 or more 2-way tapes

\smallskip\disleft 25pt:(3):
1 or more 1-way tapes

\smallskip\disleft 25pt:(4):
2 or more counters.

\smallskip\noindent
Let $L$ and $R$ be stacks, viewed as strings with the head of $L$ on the
right and the head of~$R$ on the left. (This makes it possible to view
$LR$ as a single string with a movable boundary between the two parts.)
Both are initially empty. Let $T=\langle \ldots t↓{-2},t↓{-1},t↓0,t↓1,t↓2\ldots
\rangle$ be a two-way tape, and $U=\langle u↓1,u↓2,\ldots\rangle$
a~one-way tape, both initially all blank. Let $C$ and $D$ be two counters,
initially zero.

\smallskip\disleft 25pt:(1):
To simulate $T$ using $L$ and $R$, we keep in $L$ the string
$\# t↓{-a}\ldots t↓{-2}t↓{-1}$,
and in $R$ the string $t↓0t↓1t↓2\ldots t↓b\#$, where these include
all the non-blank characters of $T$ (by induction, there are only finitely
many). Initialize $L$ and~$R$ by pushing \#\ on each. Each operation
given below is preceded by:

\smallskip\halign{\qquad\qquad\lft{\tt #}\cr
IF TOP(L)=\#\ THEN PUSH BLANK ON L;\cr
IF TOP(R)=\#\ THEN PUSH BLANK ON R;\cr}

$$\vcenter{\halign{\lft{#}\qquad&\lft{#}\cr
Operation on $T$&Simulating operation\cr
\noalign{\smallskip}
{\tt IF $t↓0={\tt X}$ THEN $\alpha$ ELSE $\beta$}&{\tt IF TOP(R)=X THEN}\cr
&\q $\alpha$ {\tt ELSE} $\beta$\cr
Move tape left&{\tt IF TOP(R)$=a↓1$ THEN PUSH $a↓1$ ON L}\cr
&{\tt ELSE IF TOP(R)$=a↓2$ THEN PUSH $a↓2$ ON L}\cr
&\q $\vdots$\cr
&{\tt ELSE IF TOP(R)$=a↓m$ THEN PUSH $a↓m$ ON L;}\cr
&\q {\tt POP R.}\cr
Move tape right&Similar, interchanging {\tt L} and {\tt R}.\cr
Write $a↓i$ on tape&{\tt POP R;}\cr
&{\tt PUSH} $a↓i$ {\tt ON R.}\cr}}$$

\smallskip\disleft 25pt:(2):
To simulate $U$ using $T$, we initially put a marker $\vdash$ on~$T$
which represents the non-existent left half of~$U$; the initialization
is

\smallskip\halign{\qquad\qquad\lft{\tt #}\cr
WRITE $\vdash$ ON T\cr
MOVE TAPE LEFT.\cr}

\smallskip\noindent
Thereafter, all operatons on $T$ are the same as on~$U$, except for:

$$\vcenter{\halign{\lft{#}\qquad&\lft{#}\cr
Operation on $U$&Operation on $T$\cr
\noalign{\smallskip}
{\tt MOVE TAPE RIGHT}&{\tt MOVE TAPE RIGHT;}\cr
&{\tt IF $t↓0=\;\vdash$ THEN}\cr
&\qq {\tt MOVE TAPE LEFT}\cr}}$$

\smallskip\disleft 25pt:(3):
To simulate $C$ and $D$ using $U$, we initialize $U$ to $\vdash$ in~$U↓1$.
$C$~and $D$ are represented by having 1's in positions $U↓2U↓4U↓6\ldots U↓{2C}$
and positions $U↓3U↓5U↓7\ldots U↓{2D+1}$, $\vdash$~in position~$U↓1$, and
blanks elsewhere. All operations on $U$ are preceded by

\smallskip\halign{\qquad\qquad\lft{\tt #}\cr
WHILE tape character $≠\;\vdash$ DO\cr
\qq MOVE TAPE RIGHT\cr}

\def\tmo{\hbox{$\vcenter{\hbox{\tt .}\vskip-8pt\hbox{\tt -}}$}} %. over -
%use $\!$ on both sides of \tmo

$$\vcenter{\halign{\lft{#}\qquad&\lft{#}\cr
Operation on $C$, $D$&Operation on $U$\cr
\noalign{\smallskip}
{\tt IF C=0 THEN $\alpha$ ELSE $\beta$}&{\tt MOVE TAPE LEFT;}\cr
&\q {\tt (* TO $U↓2$ *)}\cr
&{\tt IF} tape character $=$ blank\cr
&\q {\tt THEN $\alpha$ ELSE $\beta$}\cr
{\tt IF D=0 THEN $\alpha$ ELSE $\beta$}&{\tt MOVE TAPE LEFT;}\cr
&{\tt MOVE TAPE LEFT;}\cr
&\q {\tt (* TO $U↓3$ *)}\cr
&{\tt IF}  tape character $=$ blank\cr
&\q {\tt THEN $\alpha$ ELSE $\beta$}\cr
{\tt C:=C+1}&{\tt MOVE TAPE RIGHT;}\cr
&{\tt WHILE} tape character $=1$ {\tt DO}\cr
&\q {\tt BEGIN}\cr
&\q {\tt MOVE TAPE RIGHT}\cr
&\q {\tt MOVE TAPE RIGHT}\cr
&\q {\tt END;}\cr
&{\tt WRITE 1 ON TAPE}\cr
{\tt C:=C$\!$\tmo$\!$1}&Exercise for the reader\cr
{\tt D:=D+1}&Exercise for the reader\cr
{\tt D:=D$\!$\tmo$\!$1}&Exercise for the reader\cr}}$$

\vfill\eject

\smallskip\disleft 25pt:(4A):
To simulate several (say,~4) counters $U$, $V$, $W$, $X$ using two counters
$C$ and~$D$, at the beginning of each simulated operation we have
$2↑U3↑V5↑W7↑X$ in~$C$, and 0 in~$D$. Initially $C=1$ and $D=0$.

$$\vcenter{\halign{\lft{#}\quad&\lft{#}\cr
Typical operation on $U$, $V$, $W$, $X$&Operation on $C$, $D$\cr
\noalign{\smallskip}
Test if $V=0$&Transfer contents of $C$ to $D$ and back,\cr
&keeping track of number {\tt MOD 3}.\cr 
&If $≠0$ at the end, $V=0$.\cr
{\tt V:=V+1}&{\tt WHILE C$≠$0 DO}\cr
&\q {\tt BEGIN C:=C-1; D:=D+1 END}\cr
&{\tt WHILE D$≠$0 DO}\cr
&\q {\tt BEGIN D:=D-1; C:=C+3 END}\cr
{\tt V:=V-1}&{\tt WHILE C$≠$0 DO}\cr
&\q {\tt BEGIN C:=C-1; D:=D+1; END}\cr
&{\tt WHILE D$≠$0 DO}\cr
&\q {\tt BEGIN D:=D-3; C:=C+1 END}\cr}}$$

\smallskip\disleft 25pt:(4B):
To simulate a stack $S$ containing $x↓0x↓1x↓2\ldots x↓n$, where each $x↓i$
is, for convenience, a~1 or a~2, using counters $C$, $D$, we keep the
number $\Sigma x↓i2↑i$ in counter~$C$. Initially, the counter is~0,
corresponding to an empty stack. Our convention is that $S$ is the head
of the stack. All operations on $C$, $D$ are prefaced by setting $D=0$.

$$\vcenter{\halign{\lft{#}\quad&\lft{#}\cr
Operation on $S$&Operation on $C$, $D$\cr
\noalign{\smallskip}
Test if $S$ empty&Test if $C=0$\cr
Test if $x↓0=1$&Test if $C$ is odd\cr
Push $x$ on $C$&$C:=2C+x$\cr
Pop $C$&$C:=(C-1)\hbox{ DIV }2$\cr}}$$

\smallskip\disleft 25pt::
All the above $C$, $D$ operations are readily programmed.

\smallskip\disleft 25pt:(4):
To simulate $k$ stacks using two counters, first simulate $k+1$ counters,
then use one of them to simulate each stack, using the last, as above,
as a temporary.

\bye